package com.wj.algorithm.lintcode;

public class P187 {
    
    public int canCompleteCircuit(int[] gas, int[] cost) {
        // write your code here
        if(gas == null || gas.length < 1) {
            return -1;
        }
        
        int firstSstart = 0;
        //寻找初始起点，从油量最大的加油站开始
        int maxGasValue = 0;
        int len = gas.length;
        for(int i = 0; i < len; i ++) {
            if(gas[i] >= maxGasValue) {
                firstSstart = i;
                maxGasValue = gas[i];
            }
        }

        //每一次计算的起点
        int startIndex = firstSstart;
        //计算次数；不能超过加油站总数
        int cursorCount = 0;
        int rs = -1;
        /*
         * 初始起点不符合条件，则遍历
         * 可以优化：下次遍历从油量次大的站开始，以此类推
         */
        while(cursorCount < len){
            rs = -1;
            //某一次计算的游标
            int cursor = startIndex;
            //记录剩余汽油
            int leftGas = 0;
            //判断剩余汽油是否够用
            while((leftGas = leftGas + gas[cursor] - cost[cursor]) >= 0) {
                
                //进入这里，表示可以到达下一个，即cursor+1；所以判断下一个占是否是起始站即可
                if((cursor + 1) % len == startIndex) {
                    rs = startIndex;
                    break;
                }
                
                //游标移动到下一个站
                cursor ++;
                //环路一周
                cursor = cursor % len;
            }
            
            //有效的起始站，则直接返回，其他情况等待遍历结束
            if(rs >= 0) {
                return rs;
            }
            //计算次数+1；
            cursorCount ++;
            //下次计算开始的站点
            startIndex ++;
            //环路一周
            startIndex = startIndex % len;
        }
        
        return rs;
    }
    
    public static void main(String[] args) {
//        System.out.println(new P187().canCompleteCircuit(new int[]{1, 1, 3, 1}, new int[]{2, 2, 1, 1}));
//        System.out.println(new P187().canCompleteCircuit(new int[]{4}, new int[]{5}));
        System.out.println(new P187().canCompleteCircuit(new int[]{2,0,1,2,3,4,0}, new int[]{0,1,0,0,0,0,11}));
    }
}
